package org.example;

import guru.nidi.graphviz.engine.Format;
import guru.nidi.graphviz.engine.Graphviz;
import guru.nidi.graphviz.model.MutableGraph;
import guru.nidi.graphviz.parse.Parser;
import java.io.File;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;

/**
 * Lab1类.
 */
@SuppressWarnings("checkstyle:Indentation") // 抑制缩进警告
public class Lab1 {
    private static final Random SHARED_RANDOM = new Random();

    private static final double DAMPING_FACTOR = 0.85;  // 类级常量

    private static class Graph {
        private final Map<String, Map<String, Integer>> adjacencyList;
        private final Map<String, List<String>> inEdges;

        /**
         * Instantiates a new Graph.
         */
        public Graph() {
            adjacencyList = new HashMap<>();
            inEdges = new HashMap<>();
        }

        /**
         * Add edge.
         *
         * @param from the from
         * @param to   the to
         */
        public void addEdge(String from, String to) {
            from = from.toLowerCase();
            to = to.toLowerCase();
            adjacencyList.putIfAbsent(from, new HashMap<>());
            adjacencyList.get(from).put(to, adjacencyList.get(from).getOrDefault(to, 0) + 1);

            inEdges.putIfAbsent(to, new ArrayList<>());
            inEdges.get(to).add(from);
        }

        /**
         * Contains node boolean.
         *
         * @param word the word
         * @return the boolean
         */
        public boolean containsNode(String word) {
            word = word.toLowerCase();
            return adjacencyList.containsKey(word) || inEdges.containsKey(word);
        }

        /**
         * Gets edges.
         *
         * @param node the node
         * @return the edges
         */
        public Map<String, Integer> getEdges(String node) {
            node = node.toLowerCase();
            return adjacencyList.getOrDefault(node, Collections.emptyMap());
        }

        /**
         * Gets in nodes.
         *
         * @param node the node
         * @return the in nodes
         */
        public List<String> getInNodes(String node) {
            node = node.toLowerCase();
            return inEdges.getOrDefault(node, Collections.emptyList());
        }

        /**
         * Gets nodes.
         *
         * @return the nodes
         */
        public Set<String> getNodes() {
            Set<String> nodes = new HashSet<>();
            nodes.addAll(adjacencyList.keySet());
            nodes.addAll(inEdges.keySet());
            return nodes;
        }
    }

    private static final Graph graph = new Graph();

    /**
     * 主函数.
     *
     * @param args the input arguments
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in, StandardCharsets.UTF_8);
        System.out.println("This is the first change");
        System.out.print("Enter the text file path: ");
        String filePath = scanner.nextLine().trim();

        try {
            List<String> words = processFile(filePath);
            buildGraph(words);
            System.out.println("Graph built successfully.");
        } catch (IOException e) {
            System.out.println("Error reading file: " + e.getMessage());
            return;
        }

        while (true) {
            System.out.println("\n1. Show Directed Graph");
            System.out.println("2. Query Bridge Words");
            System.out.println("3. Generate New Text");
            System.out.println("4. Calculate Shortest Path");
            System.out.println("5. Calculate PageRank");
            System.out.println("6. Random Walk");
            System.out.println("0. Exit");
            System.out.print("Choose an option: ");
            String choice = scanner.nextLine().trim();

            switch (choice) {
                case "1":
                    String graphOutput = showDirectedGraph();
                    System.out.println("=== Directed Graph ===");
                    System.out.println(graphOutput);
                    exportGraphToImage(); // 新增导出图片
                    break;
                case "2":
                    System.out.print("Enter word1: ");
                    String word1 = scanner.nextLine().trim();
                    System.out.print("Enter word2: ");
                    String word2 = scanner.nextLine().trim();
                    System.out.println(queryBridgeWords(word1, word2));
                    break;
                case "3":
                    System.out.print("Enter text: ");
                    String inputText = scanner.nextLine();
                    System.out.println("New Text: " + generateNewText(inputText));
                    break;
                case "4":
                    System.out.print("Enter start word: ");
                    String start = scanner.nextLine().trim();
                    System.out.print("Enter end word: ");
                    String end = scanner.nextLine().trim();
                    System.out.println(calcShortestPath(start, end));
                    break;
                case "5":
                    System.out.print("Enter word: ");
                    String target = scanner.nextLine().trim();
                    Double pr = calPageRank(target);
                    System.out.println(pr != null ? "PageRank: " + pr : "Word not found.");
                    break;
                case "6":
                    System.out.println("Random Walk: " + randomWalk());
                    break;
                case "0":
                    scanner.close();
                    return;
                default:
                    System.out.println("Invalid option.");
            }
        }
    }

    static List<String> processFile(String filePath) throws IOException {
        String content = Files.readString(Paths.get(filePath));
        content = content.replaceAll("[^a-zA-Z]", " ").toLowerCase();
        return Arrays.stream(content.split("\\s+"))
                .filter(word -> !word.isEmpty())
                .toList();
    }

    static void buildGraph(List<String> words) {
        for (int i = 0; i < words.size() - 1; i++) {
            String from = words.get(i);
            String to = words.get(i + 1);
            graph.addEdge(from, to);
        }
    }

    /**
     * 在终端以字符串的方式显示有向图.
     *
     * <p>格式示例：
     * <pre>
     * A -> B(3), C(5)
     * B -> (no edges)
     * C -> A(2)
     * </pre>
     *
     * @return 代表有向图结构的字符串，每行显示一个节点及其出边
     */
    private static String showDirectedGraph() {
        StringBuilder sb = new StringBuilder();
        Lab1.graph.getNodes().forEach(node -> {
            Map<String, Integer> edges = Lab1.graph.getEdges(node);
            sb.append(node).append(" -> ");
            if (edges.isEmpty()) {
                sb.append("(no edges)\n");
            } else {
                List<String> edgeList = new ArrayList<>();
                edges.forEach((k, v) -> edgeList.add(k + "(" + v + ")"));
                sb.append(String.join(", ", edgeList)).append("\n");
            }
        });
        return sb.toString();
    }

    /**
     * 将给定的 {@link Graph} 导出为 PNG 格式的图片文件（使用 Graphviz 渲染）.
     *
     * <p>生成的图片会以 DOT 格式描述图的节点和边，并通过 Graphviz 引擎渲染为可视化图像。
     *
     * @throws IllegalArgumentException 如果参数为 null
     * @throws RuntimeException         如果 Graphviz 渲染失败（如未安装 Graphviz 或路径无效）
     * @see <a href="https://graphviz.org/">Graphviz 官网</a>
     * @since 1.0
     */
    private static void exportGraphToImage() {
        try {
            // 生成DOT格式字符串
            StringBuilder dot = new StringBuilder("digraph G {\n");
            Lab1.graph.getNodes().forEach(node -> {
                Lab1.graph.getEdges(node).forEach((neighbor, weight) -> {
                    dot.append(
                            String.format("    \"%s\" -> \"%s\" [label=\"%d\"];%n",
                                    node,
                                    neighbor,
                                    weight
                            )
                    );
                });
            });
            dot.append("}");

            // 使用Graphviz生成图片
            MutableGraph mg = new Parser().read(dot.toString());
            Graphviz.fromGraph(mg)
                    .render(Format.PNG)
                    .toFile(new File("lab1/src/main/resources/graph.png"));

            System.out.println("Graph image saved to: " + "lab1/src/main/resources/graph.png");
        } catch (Exception e) {
            System.out.println("Failed to export graph: " + e.getMessage());
        }
    }

    /**
     * 查询图中两个单词之间的桥接词（bridge words）.
     *
     * <p>桥接词定义：如果 {@code word1 -> X -> word2} 存在路径，则 X 是一个桥接词。
     *
     * <p>示例：
     * <pre>{@code
     *   graph: "apple" -> "banana" -> "cherry"
     *   queryBridgeWords("apple", "cherry") 返回 "banana"
     * }*</pre>
     *
     * @param word1 第一个单词（大小写不敏感）
     * @param word2 第二个单词（大小写不敏感）
     * @return 结果字符串 ，格式可能为：
     *      <ul>
     *          <li>"No bridge words from X to Y!"（无桥接词）</li>
     *          <li>"The bridge words from X to Y are: A, B."（多个桥接词）
     *          </li>
     *          <li>"No X/Y in the graph!"（单词不存在图中）</li>
     *      </ul>
     * @throws NullPointerException 如果任一参数为 null
     * @see #formatBridgeWords(List, String, String) #formatBridgeWords(List, String, String)
     */
    public static String queryBridgeWords(String word1, String word2) {
        final String w1 = word1.toLowerCase();
        final String w2 = word2.toLowerCase();

        if (!graph.containsNode(w1) && !graph.containsNode(w2)) {
            return "No " + w1 + " and " + w2 + " in the graph!";
        }

        if (!graph.containsNode(w1)) {
            return "No " + w1 + " in the graph!";
        }

        if (!graph.containsNode(w2)) {
            return "No " + w2 + " in the graph!";
        }

        List<String> bridges = new ArrayList<>();
        graph.getEdges(w1).keySet().forEach(candidate -> {
            if (graph.getEdges(candidate).containsKey(w2)) {
                bridges.add(candidate);
            }
        });

        if (bridges.isEmpty()) {
            return "No bridge words from " + w1 + " to " + w2 + "!";
        }
        return formatBridgeWords(bridges, w1, w2);
    }

    private static String formatBridgeWords(List<String> bridges, String word1, String word2) {
        StringBuilder sb = new StringBuilder();

        sb.append("The bridge words from ")
                .append(word1)
                .append(" to ")
                .append(word2)
                .append(" are: ");

        for (int i = 0; i < bridges.size(); i++) {
            if (i == bridges.size() - 1 && bridges.size() > 1) {
                sb.append("and ");
            }
            sb.append(bridges.get(i)).append(i < bridges.size() - 2 ? ", " : "");
        }
        return sb.append(".").toString();
    }

    /**
     * 根据输入文本生成新文本，在相邻的合法单词之间随机插入桥接词（如果存在）.
     *
     * <p>处理逻辑：
     * <ol>
     *     <li>将输入文本按非字母字符拆分为单词数组（忽略连续非字母字符）。</li>
     *     <li>遍历相邻单词对，查询图中是否存在桥接词（通过 {@link #queryBridgeWords} 逻辑）。</li>
     *     <li>若存在桥接词，随机选择一个插入到原单词之间。</li>
     * </ol>
     *
     * <p>示例：
     * <pre>{@code
     *   输入: "apple cherry"
     *   假设图中存在路径 "apple -> banana -> cherry"
     *   输出可能为: "apple banana cherry"
     * }*</pre>
     *
     * @param inputText 原始输入文本（非空，可包含标点）
     * @return 生成的新文本 （单词间用空格连接）
     * @throws IllegalArgumentException 如果输入为 null 或空字符串
     * @see #queryBridgeWords(String, String) #queryBridgeWords(String, String)
     * @since 1.0
     */
    public static String generateNewText(String inputText) {
        String[] words = inputText.split("[^a-zA-Z']+");
        List<String> newText = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i].isEmpty()) {
                continue;
            }

            newText.add(words[i]);
            if (i < words.length - 1 && !words[i + 1].isEmpty()) {
                String word1 = words[i].toLowerCase();
                String word2 = words[i + 1].toLowerCase();
                List<String> bridges = new ArrayList<>();
                if (graph.containsNode(word1) && graph.containsNode(word2)) {
                    graph.getEdges(word1).keySet().forEach(candidate -> {
                        if (graph.getEdges(candidate).containsKey(word2)) {
                            bridges.add(candidate);
                        }
                    });
                }
                if (!bridges.isEmpty()) {
                    newText.add(bridges.get(SHARED_RANDOM.nextInt(bridges.size())));
                }
            }
        }
        return String.join(" ", newText);
    }

    /**
     * 计算图中两个单词之间的最短路径（使用 Dijkstra 算法或其他实现）.
     *
     * <p>行为说明：
     * <ul>
     *     <li>若未提供 {@code word2}，则计算 {@code word1} 到图中所有其他节点的最短路径。</li>
     *     <li>路径格式为 "word1 -> nodeA -> ... -> word2 (total weight: X)"。</li>
     *     <li>若单词不存在或路径不存在，返回错误提示。</li>
     * </ul>
     *
     * <p>示例：
     * <pre>{@code
     *   输入: ("apple", "cherry")
     *   输出: "apple -> banana -> cherry (total weight: 2)"
     *
     *   输入: ("apple", null)
     *   输出: "apple -> banana (total weight: 1)\n apple -> cherry (total weight: 3)"
     * }*</pre>
     *
     * @param word1 起始单词（大小写不敏感）
     * @param word2 目标单词（可为 null 或空，表示计算到所有节点的路径）
     * @return 路径结果字符串或错误信息 ：
     *      <ul>
     *          <li>若单词不存在：返回 "Word not found."</li>
     *          <li>若无其他节点：返回 "No other nodes in graph."</li>
     *      </ul>
     * @throws NullPointerException 如果 {@code word1} 为 null
     * @see #calcSinglePath(String, String) #calcSinglePath(String, String)
     */
    public static String calcShortestPath(String word1, String word2) {
        word1 = word1.toLowerCase();

        if (!graph.containsNode(word1)) {
            return "Word not found.";
        }

        // 若未输入第二个单词，计算到所有节点的路径
        if (word2 == null || word2.isEmpty()) {
            StringBuilder sb = new StringBuilder();
            String finalWord = word1;
            graph.getNodes().forEach(target -> {
                if (!target.equals(finalWord)) {
                    sb.append(calcSinglePath(finalWord, target)).append("\n");
                }
            });
            return sb.toString().isEmpty() ? "No other nodes in graph." : sb.toString();
        }

        word2 = word2.toLowerCase();
        return calcSinglePath(word1, word2);
    }

    private static String calcSinglePath(String word1, String word2) {
        word1 = word1.toLowerCase();
        word2 = word2.toLowerCase();
        if (!graph.containsNode(word1) || !graph.containsNode(word2)) {
            return "No path exists.";
        }

        final Map<String, Integer> dist = new HashMap<>();
        final Map<String, String> prev = new HashMap<>();
        PriorityQueue<NodeDist> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.dist));
        graph.getNodes().forEach(node -> dist.put(node, Integer.MAX_VALUE));
        dist.put(word1, 0);
        pq.add(new NodeDist(word1, 0));

        while (!pq.isEmpty()) {
            NodeDist current = pq.poll();

            if (current.dist > dist.get(current.node)) {
                continue;
            }

            graph.getEdges(current.node).forEach((neighbor, weight) -> {
                int newDist = current.dist + weight;
                if (newDist < dist.get(neighbor)) {
                    dist.put(neighbor, newDist);
                    prev.put(neighbor, current.node);
                    pq.add(new NodeDist(neighbor, newDist));
                }
            });
        }

        if (dist.get(word2) == Integer.MAX_VALUE) {
            return "No path exists.";
        }
        List<String> path = new LinkedList<>();
        for (String node = word2; node != null; node = prev.get(node)) {
            path.addFirst(node);    // path.add(0, node);
        }
        return "Path: " + String.join(" -> ", path) + " (Length: " + dist.get(word2) + ")";
    }

    private static class NodeDist {
        /**
         * The Node.
         */
        String node;
        /**
         * The Dist.
         */
        int dist;

        /**
         * Instantiates a new Node dist.
         *
         * @param node the node
         * @param dist the dist
         */
        NodeDist(String node, int dist) {
            this.node = node;
            this.dist = dist;
        }
    }

    /**
     * 计算指定单词的 PageRank 值（基于带词频初始化的改进算法）.
     *
     * <p>算法特性：
     * <ol>
     *   <li><b>初始化：</b>使用节点的出边词频（TF）归一化作为初始 PR 值</li>
     *   <li><b>阻尼因子：</b>固定为 0.85，模拟随机跳转概率</li>
     *   <li><b>收敛条件：</b>连续两次迭代的 PR 值差均小于 1e-6 或达到最大迭代次数（100次）</li>
     *   <li><b>处理悬挂节点：</b>将其 PR 值均分给所有其他节点</li>
     * </ol></p>
     *
     * <p><b>特殊处理：</b><br>
     * 当所有节点出度为 0 时，退化为均匀分布初始值（1/节点总数）。</p>
     *
     * @param word 要查询的单词（大小写不敏感）
     * @return 该单词的 PageRank 值，若单词不在图中返回 {@code null}
     * @throws NullPointerException 若参数为 {@code null}
     */
    public static Double calPageRank(String word) {
        final String target = word.toLowerCase();

        if (!graph.containsNode(target)) {
            return null;
        }

        final Set<String> nodes = graph.getNodes();
        final int N = nodes.size();

        if (N == 0) {
            return 0.0;
        }

        Map<String, Double> currentPr = new HashMap<>();

        // 计算词频（TF）
        Map<String, Integer> wordFrequency = new HashMap<>();
        graph.getNodes().forEach(node -> {
            int freq = graph.getEdges(node).values().stream().mapToInt(Integer::intValue).sum();
            wordFrequency.put(node, freq);
        });

        // 归一化初始PR值
        double sum = wordFrequency.values().stream().mapToDouble(v -> v).sum();
        if (sum == 0) {
            // 所有节点出度为0，回退到均匀分布
            Map<String, Double> finalCurrentPr = currentPr;
            nodes.forEach(node -> finalCurrentPr.put(node, 1.0 / N));
        } else {
            Map<String, Double> finalCurrentPr3 = currentPr;
            nodes.forEach(node -> {
                double prInit = wordFrequency.get(node) / sum;
                finalCurrentPr3.put(node, prInit);
            });
        }

        final double teleport = (1 - DAMPING_FACTOR) / N;
        int maxIter = 100;

        for (int iter = 0; iter < maxIter; iter++) {
            Map<String, Double> newPr = new HashMap<>();

            // 计算所有出度为0的节点的总贡献，finalCurrentPr1.get(u) = finalCurrentPr1::get
            Map<String, Double> finalCurrentPr1 = currentPr;
            double sinkSum = nodes.stream()
                    .filter(u -> graph.getEdges(u).isEmpty())
                    .mapToDouble(finalCurrentPr1::get)
                    .sum() / N;

            Map<String, Double> finalCurrentPr2 = currentPr;
            nodes.forEach(node -> {
                // 入边贡献（仅处理出度>0的节点）
                double incomingSum = graph.getInNodes(node).stream()
                        .mapToDouble(u -> {
                            int outDegree = graph.getEdges(u).size();
                            return outDegree > 0 ? finalCurrentPr2.get(u) / outDegree : 0.0;
                        })
                        .sum();

                // 总贡献 = 入边贡献 + 出度0节点的均分贡献
                double total = incomingSum + sinkSum;
                newPr.put(node, teleport + DAMPING_FACTOR * total);
            });

            if (converged(currentPr, newPr)) {
                break;
            }

            currentPr = new HashMap<>(newPr);
        }
        return currentPr.get(target);
    }


    private static boolean converged(Map<String, Double> oldPr, Map<String, Double> newPr) {
        return oldPr.keySet().stream()
                .allMatch(node -> Math.abs(oldPr.get(node) - newPr.get(node)) < 1.0E-6);
    }

    /**
     * 在图中执行随机游走，并将路径保存到文件.
     *
     * <p>从随机选择的节点开始，按边的权重随机遍历相邻节点，直到遇到以下情况停止：
     * <ul>
     *   <li>当前节点无出边（死胡同）</li>
     *   <li>重复经过同一条边（防止环路无限循环）</li>
     * </ul>
     * 结果路径会保存到 {@code lab1/src/main/resources/random_walk.txt} 文件中。</p>
     *
     * <p><b>示例输出：</b><br>
     * 若路径为 A → B → C，返回值为 {@code "A B C"}，文件内容相同。</p>
     *
     * @return 随机游走的路径字符串 （空格分隔节点），若图为空返回空字符串 {@code ""}
     * @throws SecurityException 若无权限写入文件
     */
    public static String randomWalk() {
        List<String> nodes = new ArrayList<>(graph.getNodes());

        if (nodes.isEmpty()) {
            return "";
        }

        String current = nodes.get(SHARED_RANDOM.nextInt(nodes.size()));
        List<String> path = new ArrayList<>();
        Set<String> visitedEdges = new HashSet<>();
        path.add(current);

        while (true) {
            Map<String, Integer> edges = graph.getEdges(current);

            if (edges.isEmpty()) {
                break;
            }

            List<String> candidates = new ArrayList<>(edges.keySet());
            String next = candidates.get(SHARED_RANDOM.nextInt(candidates.size()));
            String edge = current + "->" + next;

            if (visitedEdges.contains(edge)) {
                break;
            }

            visitedEdges.add(edge);
            path.add(next);
            current = next;
        }

        try {
            Path outputPath = Paths.get("lab1/src/main/resources/random_walk.txt");
            Files.writeString(outputPath, String.join(" ", path));
            System.out.println("Random walk saved to: " + outputPath.toAbsolutePath());
        } catch (IOException e) {
            System.out.println("Failed to save random walk: " + e.getMessage());
        }
        return String.join(" ", path);
    }
}